#include <stdio.h>

char DIGITS[] = "0123456789ABCDEF";

int main()
{
    int nCase;
    for (scanf("%d", &nCase); nCase--;)
    {
        int d, x, b[32], i = 0;
        scanf("%d%d", &d, &x);
        do {
            b[i++] = d % x;
            d /= x;
        } while (d > 0);
        while (i > 0)
            printf("%c", DIGITS[b[--i]]);
        printf("\n");
    }
    return 0;
}
